package com.java.comprehensive.arithmetic.leecode.tags.array;

/**
 * @Author: 窦绍飞
 * @Date: 2022/6/26
 */
public class LeetCode_31 {

	public static void nextPermutation(int[] nums) {

		int n = nums.length;
		if (n < 1) return;

		int i = n - 2;
		while (i >= 0 && nums[i] >= nums[i + 1]) {
			i--;
		}

		if (i < 0) {
			//到这里证明数组已经是个倒序列了 ，翻转
			reverse(nums, 0, n);
		} else {
			int j = n - 1;

			//根据l-2,判断之前i重新排列之后的应该在哪个位置
			//n-2 和 n-2对应需要调换顺序的值
			while (i < j && nums[j] <= nums[i]) j--;

			int temp = nums[i];
			nums[i] = nums[j];
			nums[j] = temp;
			//到这里证明数组已经将排列好 需要翻转
			reverse(nums, i + 1, n - 1);
		}

	}

	public static void reverse(int[] nums, int start, int end) {
		while (start < end) {
			int temp = nums[start];
			nums[start] = nums[end];
			nums[end] = temp;
			start++;
			end--;
		}

	}

	public static void main(String[] args) {
		int[] nums = {1, 4, 3, 2, 0};
		nextPermutation(nums);
		System.out.println(nums);
	}
}
